Homework 02: LP formulations Here's some good general math modeling advice: if you aren't sure that your formulation is right, do this: a) make a copy of it (in a spreadsheet, do move-or-copy/create-a-copy on the whole tab) b) on that copy, fill in simpler values so you know what the answer should be. For example: - in an assignment problem, make it obvious which things are the least costly, and make them not conflict - in a problem with demand, either set all demands equal to each other, or set most demands to zero but one demand nonzero. The same way that science experiments often have "controls", you could call these your "control" problems. c) Modify your model on the control problem until it gives what you know are the right answers. d) Do not go back and try to make the same modifications to your original sheet; that would be error-prone. e) Instead, do move-or-copy/make-a-copy on the now-fixed control sheet, and on that new copy, fill in the original parameter values, and re-solve. There are two versions of this assignment: one using the Winston book, which you might not have bought, or a free online PDF of a chapter from Hillier and Lieberman (link shown below) I feel that the Winston version is better (leads to more learning), but of course you can only do it if you have that book. Remember that there can be only one Solver model per sheet, so each problem (or even sub-problem) should get its own sheet. In class, we formulated things in Excel/Solver and also wrote things like minimize cost: $0.50 M + $0.16 R s.t. 190 M + 530 R >= 2000 and you'll see formulations like that in the reading as well. While those types of formulations are good to practice and might help in organizing your Solver work, and you're free to do them if you like, I'm not requiring them on this homework. The reason is, when writing formulations in Solver, there's an automated way to check if what you're writing doesn't make sense--Solver will give you error messages or nonsense results. We'll work later on math-formula formulations like that. Remember that you're encouraged to work together on homework, though it should be collaborative rather than dividing the problems between yourselves. ---------------------------------------------- Hillier and Lieberman, Chapter 3: http://www.mhhe.com/engcs/industrial/hillier/etext/PDF/chap03.pdf (also, there's a copy in our online course shell in case that link ever breaks) For each of these, formulate it in Excel (or similar) and use Solver to solve it. You do not have to do any graphical solutions, though of course if you want to check your work that way, okay. Try using desmos.com to do the graphical solutions if you like. 3.1-7 Apex Television 3.1-8 WorldLight 3.4-7 steak & potatoes 3.4-9 leasing space. Hint: final obj.func.val = $7,650,000 3.4-10 staffing, 4-hour blocks, full & part time. Hint: final obj.func.val = $1,493.333 if fractional; $1,504.00 if integer. 3.4-14 blending metals for alloy. Hint: $23.46 3.4-16 plane loading/balancing. Hint: $13,330.00 Other (mandatory!) questions: Question A: Why don't we allow an LP to have < or > constraints? (as opposed to <= or >= ) Question B: True or False, and explain: for an LP to be unbounded, the LP's feasible region must be unbounded. Question C: True or False, and explain: Every LP with an unbounded feasible region is an Unbounded LP. Question D: Busville problem: http://books.google.com/books?id=ZKuciHd-vaQC&lpg=PA56&ots=OvUTHkRSdS&dq=%22The%20city%20of%20Busville%22&pg=PA56#v=onepage&q=%22The%20city%20of%20Busville%22&f=false Based on Franklin and Koenigsberg (1973): The city of Busville contains three school districts. The number of minority and non-minority students in each district are: District #Minority #Non-minority 1 50 200 2 50 250 3 100 150 Of all students, 25% are minority students. The local court has decided that both of the town's schools (Cooley High and Walt Whitman High) must have approximately the same percentage of minority students (within +/- 5%) as the entire town. The distances (in miles) between the school districts and the high schools are given here: District Cooley Whitman 1 1 2 2 2 1 3 1 1 Each high school must have an enrollment between 300 and 500 students. Determine an assignment of students to schools that minimizes the total distance students must travel to school. Formulate it and solve it in Solver. Hint: final obj.func.val = 800 Note that the original problem in Richmond in Northern California had 45 elementary schools and 20,000 students, and required a +/- 15% (actually percentage points) margin, by state law. Their model would have 981 constraints and 36,000 variables, but they were unable to solve it. Question E: Inventory and Production Decisions Read the "Sailco" PDF supplied by the professor, in our Course Shell. Then: i) Implement the model worked out in Example 14 in Solver; make sure it gives the right answer. ii) If you've talked about networks, try to diagram it as a network. You don't have to have supplies coming from a node, though. It's hard to sketch diagrams in Excel; just do it on paper to discuss with me in person. iii) What happens if you make overtime cheaper than ordinary production time? iv) Copy your Solver sheet; in the copy, implement production-smoothing constraints on Regular labor (not overtime), so the production amount doesn't increase by more than 5 or drop by more than 7 from one period to the next. Hint: 78900 v) Copy your Solver sheet from part (i); in the copy, implement a warehouse-building cost. You don't own a warehouse yet. You have to build it to suit your production/inventory plan, and it costs $1000 per unit capacity. You need to build it large enough to handle the _largest_ inventory you plan to hold. This is in addition to all other costs in the problem. hint: 78750 ----------------------------------------------- Wayne Winston, Chapter 3: Chapter 3.1 1 Farmer Jones, how much corn & wheat 2 Is (?,?) in the feasible region? 4 Truckco, how many Type 1 & 2 trucks: if just Type 1, then 800/day could be painted... 5 Why don't we allow an LP to have < or > constraints? (as opposed to <= or >= ) Ch 3.2 Graphical Solutions read it, but no exercises required Ch 3.3 Special Cases 5 T/F and explain: for an LP to be unbounded, the LP's feasible region must be unbounded 6 T/F and explain: Every LP with an unbounded feasible region has an unbounded optimal solution 7 If bounded feasible region, could just check z-value at each feasible extreme point. Why might it fail if feasible region is unbounded? Ch 3.4 Diet Problem 1 Three factories, processing waste, minimize cost of reducing 2 pollutants by specified amounts 2 Heart valves from pigs 3 Peg and Al Fundy; oversatisfy vitamin C requirement at optimality; what if we require no waste of Vitamin C? Ch 3.5 Work-Scheduling: choose any 2 of these: 1 Post-office scheduling, full & part time, 7 days 2 Police force, 24 hours, 4-hour blocks, shift=8 consecutive hours 3 Post office, forced 1-day overtime 4 Post office, <= 25 full-time, maximize weekend days off 5 Police, 6-hour shifts, non-consecutive allowed Ch 3.6 Capital Budgeting read it, but no exercises required Ch 3.7 Short-Term Financial Planning read it, but no exercises required Ch 3.8 Blending Problems 1 two kinds of candy, >= __% nuts, >= __% chocolate, maximize revenue 9 bond portfolio, expected return & worst-case return 13 Manager says example solution can't be right since it doesn't use all resources. What do you say? Ch 3.9 Production Process 1 Refining, multiple inputs and outputs Ch 3.10 multiperiod inventory, Sailco 1 four months of demand, known production costs, storage costs, salvage value Ch 3.11 Multiperiod financial models read it, but no exercises required Ch 3.12 Multiperiod work scheduling read it, but no exercises required Review Problems (notice that in the review problems, you don't know which of the sections 3.1 to 3.12 the problem is most like, and that is on purpose!) 8 Orchard, wheat and corn, meet demand at minimum cost 18 Minority busing, 25% minority, get +/- 5% matching 19 Cabinets, 2 lumber sources 20 Parks commission, spruce or hunting or camping or both 24 hospital bed-days 57 Tankering (hard! read it and wait for help) 59 (optional) Kirchoff's voltage and current laws